package leetcode_800;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.TreeMap;

public class NumberOfAtoms_726_ {
	/**
	 * describe:用栈和MAP AC 74%
	 * 2018年10月13日 下午3:11:58 
	 * Map里只放值 如OH -> 2 最后再排序
	 */
	public String countOfAtoms(String formula) {
        Stack<Map<String,Integer>> stack= new Stack<>();
        Map<String,Integer> map= new HashMap<>();
        int i=0,n=formula.length();
        while(i<n){
            char c=formula.charAt(i);i++;
            if(c=='('){
                stack.push(map);//这个map立马入栈 这个map是保存这次遍历的值
                map=new HashMap<>();//map又重新实例化
            }
            else if(c==')'){
                int val=0;
                while(i<n && Character.isDigit(formula.charAt(i)))//括号后面必须跟数字
                    val=val*10+formula.charAt(i++)-'0';

                if(val==0) val=1;
                if(!stack.isEmpty()){
                Map<String,Integer> temp= map;
                map=stack.pop();//把上一个栈里的取出来然后乘  再放进去
                    for(String key: temp.keySet())
                        map.put(key,map.getOrDefault(key,0)+temp.get(key)*val);
                }
            }
            else{
                int start=i-1;
                while(i<n && Character.isLowerCase(formula.charAt(i))){//如果是小字母那么立即往下遍历
                 i++;
                }
                String s= formula.substring(start,i);//截取字符串
                int val=0;
                while(i<n && Character.isDigit(formula.charAt(i))) val=val*10+ formula.charAt(i++)-'0';//开始截取数字并累加这个数字
                if(val==0) val=1;
                map.put(s,map.getOrDefault(s,0)+val);//存入所有stack的和
            }
        }
        StringBuilder sb= new StringBuilder();
        List<String> list= new ArrayList<String>(map.keySet());
        Collections.sort(list);
        for(String key: list){ 
            sb.append(key);
          if(map.get(key)>1) sb.append(map.get(key));
                                    }
        return sb.toString();
    }
	int i;
    
    /**
     * describe:截取字符串递归 我认为不算是很好的办法
     * 2018年10月13日 下午3:10:50
     */
    public String countOfAtoms1(String formula) {
        StringBuilder ans = new StringBuilder();
        i = 0;
        Map<String, Integer> count = parse(formula);
        for (String name: count.keySet()) {
            ans.append(name);
            int multiplicity = count.get(name);
            if (multiplicity > 1) 
                ans.append("" + multiplicity);
        }
        return new String(ans);
    }

    public Map<String, Integer> parse(String formula) {
        int N = formula.length();
        Map<String, Integer> count = new TreeMap();
        while (i < N && formula.charAt(i) != ')') {
            if (formula.charAt(i) == '(') {
                i++;
                for (Map.Entry<String, Integer> entry: parse(formula).entrySet()) {
                    count.put(entry.getKey(), count.getOrDefault(entry.getKey(), 0) + entry.getValue());
                }
            } else {
                int iStart = i++;
                while (i < N && Character.isLowerCase(formula.charAt(i))) 
                    i++;
                String name = formula.substring(iStart, i);
                iStart = i;
                while (i < N && Character.isDigit(formula.charAt(i))) 
                    i++;
                int multiplicity = iStart < i ? Integer.parseInt(formula.substring(iStart, i)) : 1;
                count.put(name, count.getOrDefault(name, 0) + multiplicity);
            }
        }

        int iStart = ++i;

        while (i < N && Character.isDigit(formula.charAt(i))) 
            i++;

        if (iStart < i) {
            int multiplicity = Integer.parseInt(formula.substring(iStart, i));
            for (String key: count.keySet()) {
                count.put(key, count.get(key) * multiplicity);
            }
        }
        return count;
    }
}
